/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 邓大帅
 * Date: 2023-02-22
 * Time: 19:12
 */
public class Sort3 {
    // 归并排序---递归
    public static void mergeSort(int[] array) {
        mergeSortFunc(array, 0, array.length-1);
    }
    private static void mergeSortFunc(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSortFunc(array, left, mid);
        mergeSortFunc(array, mid+1, right);
        merge(array, left, mid, right);
    }
    private static void merge(int[] array, int left, int mid, int right) {
        int s1 = left;
        int s2 = mid+1;
        int n = (right - left) / 2;
        int[] arr = new int[n];
        int k = 0;
        while (s1 <= mid && s2 <= right) {
            if(array[s1] < array[s2]) {
                arr[k++] = array[s1++];
            }else {
                arr[k++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            arr[k++] = array[s1++];
        }
        while (s2 <= right) {
            arr[k++] = array[s2++];
        }
        for (int i = 0; i < arr.length; i++) {
            array[i+left] = arr[i];
        }
    }

    // 归并排序---非递归
    public static void mergeSort1(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            // i += gap * 2 当前gap组的时候，去排序下一组
            for (int i = 0; i < array.length; i += gap * 2) {
                int left = i;
                int mid = left+gap-1;//有可能会越界
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+gap;//有可能会越界
                if(right>= array.length) {
                    right = array.length-1;
                }
                merge(array,left,right,mid);
            }
            //当前为2组有序  下次变成4组有序
            gap *= 2;
        }
    }

    // 计数排序
    public static void countSort(int[] array) {
        //1. 遍历数组 找到最大值 和 最小值
        int max = array[0];
        int min = array[0];
        //O(N)
        for (int i = 1; i < array.length; i++) {
            if(array[i] < min) {
                min = array[i];
            }
            if(array[i] > max) {
                max = array[i];
            }
        }
        //2. 根据范围 定义计数数组的长度
        int len = max - min + 1;
        int[] count = new int[len];
        //3.遍历数组，在计数数组当中 记录每个数字出现的次数 O(N)
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }
        //4.遍历计数数组
        int index = 0;// array数组的新的下标 O(范围)
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                //这里要加最小值  反应真实的数据
                array[index] = i+min;
                index++;
                count[i]--;
            }
        }
    }
}
